The present invention relates to an image line-segment extracting apparatus which is capable of extracting line segments from a picture image by applying the Hough transformation method.
Each dot (x, y) in a sequence of pixels composing a line segment L in a two-dimensional system of the Cartesian coordinates (x, y), as shown for example in FIG. 6, can be transformed into a curve represented by a Hough function in terms of (.rho.=x*cos .theta.+y*sin .theta.) with Hough coordinates (.rho., .theta.) as shown in FIG. 7. The curves intersect each other at a point (dot) Po (.rho.o, .theta.o) with the Hough coordinates (.rho., .theta.). The intersection point Po represents a straight line including the line segment L shown in the two-dimensional system of the coordinates (x, y).
When a histogram is plotted for values of the functions of the dots composing the line segment L, the above-mentioned intersection point Po can be determined by detecting a peak of the maximum frequency (occurrence) on the histogram. Consequently, it is possible to recognize that the line segment L is a sequence of dots (pixels) with their coordinates (x, y), which corresponds to Hough function curves passing through the intersect ion point Po (a peak on the histogram).
On the basis of the above-described conception, such an image line-segment extracting apparatus has been developed, which is capable of extracting line segments from a picture image by conducting the following steps: a sequence of dots composing an edge of an image, which is obtained by differential processing of a digitized image composed of pixels, is transformed into curves of Hough functions; a histogram is plotted for the values of the Hough functions; a peak of frequency on the histogram is detected; and a line segment corresponding to the detected peak is extracted from the picture image.
The thus constructed apparatus, however, encounters a trouble that, in case of an image including two or more line segments, Hough functions of the line segments interfere with each other to locally produce false peaks on their histograms, which interfere with extraction of each line segment corresponding to a true peak (a peak produced by a line segment really existing in the image).
In other words, when an image includes a plurality of line segments, Hough function curves of the line segments intersect with each other to produce false peaks near each true peak corresponding to the intersection point of Hough function curves of a line segment to be extracted.
For example, in the prior art methods when dots Q1 to Q4 at both ends of line segments La, Lb and Lc with coordinates (x, y) shown in FIG. 8 are transformed by Hough transform method, thereby the Hough function curves C1 to C4 with Hough coordinates (.rho., .theta.) shown in FIG. 9 are obtained.
In FIG. 9, the Hough's function curves C1, C2, C3 and C4 correspond to the dots Q1, Q2, Q3 and Q4 respectively. Pa, Pb and Pc indicate true peaks of a histogram, which correspond to the line segments La, Lc and Lc respectively.
The histogram may include many false peaks that may appear as indicated by black squares in FIG. 9. These false peaks appear mostly in regions wherein the true peaks Pa, Pb and Pc corresponding to the respective line segments La, Lb and Lc influence on each other. Some of these false peaks may have larger values of histogram frequency than those of the true peaks Pa and Pc.
Accordingly, an attempt to successively extract the line segments existing in the image by subsequently detecting peaks on the histogram according to frequency in descending order may result in the selection of false peaks because of their frequency values being larger than those of the true peaks.
To prevent this, a prior art system employs the following method that is disclosed in Japanese laid-open patent publication No. 74680 of 1988:
Based on the fact that the maximum peak on a histogram surely corresponds to a line segment in an image, the prior art detects the maximum peak first from the histogram and, at the same time, determines all Hough function curves passing through the detected peak point, then it plots a new histogram from which the determined curves are eliminated and detects therefrom the second maximum peak.
However, the above-mentioned method requires a large amount of calculation for newly plotting a histogram to eliminate false peaks at every time of detecting a maximum peak from a histogram, causing the processing system to be overloaded.